package com.gitee.swsk33.algorithms.sort.util;

import java.util.Arrays;

import static com.gitee.swsk33.algorithms.sort.util.BasicSort.swap;

/**
 * 高级排序算法
 */
public class AdvanceSort {

	/**
	 * 希尔排序
	 *
	 * @param array 待排序数组
	 */
	public static void shellSort(int[] array) {
		int j, temp, increment = array.length;
		do {
			increment = increment / 3 + 1;
			// 把相隔increment增量的元素进行插入排序
			for (int i = increment; i < array.length; i++) {
				if (array[i] < array[i - increment]) {
					temp = array[i];
					for (j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
						array[j + increment] = array[j];
					}
					array[j + increment] = temp;
				}
			}
		} while (increment > 1);
	}

	/**
	 * 堆排序-调整二叉树中部分范围子树为大根堆，由于二叉树中结点索引从1开始，因此对数组进行操作时，下标会减1
	 * 二叉树性质：假设根节点编号为1，按照层次遍历从上至下、从左到右给二叉树结点编号，那么对于编号为i的结点，其左孩子编号为2i，右孩子为2i + 1
	 *
	 * @param array 待排序列表，可看做顺序储存的二叉树
	 * @param start 调整的双亲结点索引（从1开始）
	 * @param end   调整的最后一个子节点索引（从1开始）
	 */
	private static void heapAdjust(int[] array, int start, int end) {
		// 从双亲结点的第一个左孩子开始
		for (int i = 2 * start; i <= end; i *= 2) {
			// 先从左右孩子中挑出较大的那个
			if (i < end && array[i - 1] < array[i]) {
				i++;
			}
			// 和双亲结点比较，若双亲结点比其小则交换
			if (array[i - 1] > array[start - 1]) {
				swap(array, i - 1, start - 1);
				start = i;
			}
		}
	}

	/**
	 * 堆排序
	 *
	 * @param array 待排序数组
	 */
	public static void heapSort(int[] array) {
		// 第一步：先把整个数组构建成大根堆
		// 堆调整函数应当是从最后一个双亲结点开始逐步向上调用
		for (int i = array.length / 2; i > 0; i--) {
			heapAdjust(array, i, array.length);
		}
		// 第二步：每次拿出大根堆的根节点放到最后，然后把剩下的元素构成大根堆，直到排序完成
		for (int i = array.length - 1; i > 0; i--) {
			swap(array, i, 0);
			// 传入的是二叉树结点索引
			heapAdjust(array, 1, i);
		}
	}

	/**
	 * 将数组的两部分有序序列归并为一部分有序序列
	 *
	 * @param array 归并数组
	 * @param start 第一部分起始索引
	 * @param mid   第一部分终止索引
	 * @param end   第二部分终止索引
	 */
	private static void merge(int[] array, int start, int mid, int end) {
		// 先用两个辅助数组把array的start到mid - 1与mid到end这两部分存起来，然后有序归并回array
		int leftLength = mid - start + 1; // 左辅助数组长度
		int rightLength = end - mid;      // 右辅助数组长度
		int[] leftSubArray = Arrays.copyOfRange(array, start, mid + 1);
		int[] rightSubArray = Arrays.copyOfRange(array, mid + 1, end + 1);
		// 开始归并
		// 左右辅助数组的下标指针
		int leftIndex = 0, rightIndex = 0;
		// 当左辅助数组当前元素比右辅助数组的小，则插入进原列表完成归并
		// 如果说当前左辅助数组都被插入完了，那就说明小的都归并完了，直接到else归并右辅助数组的元素
		// 反过来如果说当前右辅助数组都被插入完了，那么只需归并左辅助数组元素即可
		for (int i = start; i <= end; i++) {
			if (rightIndex >= rightLength || (leftIndex < leftLength && leftSubArray[leftIndex] < rightSubArray[rightIndex])) {
				array[i] = leftSubArray[leftIndex];
				leftIndex++;
			} else {
				array[i] = rightSubArray[rightIndex];
				rightIndex++;
			}
		}
	}

	/**
	 * 归并排序的递归部分
	 *
	 * @param array 待排序数组
	 * @param start 排序范围起始下标
	 * @param end   排序范围终止下标
	 */
	private static void mergeSortRecursive(int[] array, int start, int end) {
		// 若当前范围只有一个元素，就不用排了
		if (start >= end) {
			return;
		}
		// 范围一分为二
		int mid = (start + end) / 2;
		// 二路归并排序
		mergeSortRecursive(array, start, mid); // 先递归排序左半部分
		mergeSortRecursive(array, mid + 1, end); // 然后递归排序右半部分
		merge(array, start, mid, end); // 归并融合为有序序列
	}

	/**
	 * 归并排序-递归版
	 *
	 * @param array 待排序数组
	 */
	public static void mergeSortR(int[] array) {
		mergeSortRecursive(array, 0, array.length - 1);
	}

	/**
	 * 把array分为若干个长度为subLength的子序列，然后对它们两两进行归并
	 *
	 * @param array     待归并的数组
	 * @param subLength 子序列长度
	 */
	private static void mergePass(int[] array, int subLength) {
		int count = array.length / subLength; // 前面可均分的子序列个数
		int groupCount = count / 2; // 前面可一次归并的子序列组数，2个为1组
		int remain = array.length % subLength; // 剩余未被均分的元素个数
		// 开始两两归并
		for (int i = 0; i < groupCount; i++) {
			merge(array, i * 2 * subLength, (i * 2 + 1) * subLength - 1, (i + 1) * 2 * subLength - 1);
		}
		// 对剩下未归并的组进行归并
		if (count % 2 == 1 && remain != 0) {
			merge(array, groupCount * 2 * subLength, (groupCount * 2 + 1) * subLength - 1, array.length - 1);
		}
	}

	/**
	 * 归并排序-非递归
	 *
	 * @param array 待排序数组
	 */
	public static void mergeSort(int[] array) {
		// i表示子序列长度，先开始为1
		for (int i = 1; i < array.length; i *= 2) {
			mergePass(array, i);
		}
	}

	/**
	 * 选取枢轴变量，并把小的移动到枢轴前面，大的移动至后面，最终返回枢轴变量的下标
	 * 使用三数取中法
	 *
	 * @param array 待排序的数组
	 * @param start 排序起始索引
	 * @param end   排序终止索引
	 * @return 枢轴变量的下标
	 */
	private static int partition(int[] array, int start, int end) {
		// 计算中间索引
		int mid = start + (end - start) / 2;
		// 先保证最左比最右小
		if (array[start] > array[end]) {
			swap(array, start, end);
		}
		// 然后保证中间比最右边小
		if (array[mid] > array[end]) {
			swap(array, mid, end);
		}
		// 最后，把中等值移动到最左
		if (array[mid] > array[start]) {
			swap(array, start, mid);
		}
		// 此时，start指向枢轴变量，为中间值
		int pivot = array[start];
		// 移动使得大的都在枢轴右边，小的都在左边
		while (start < end) {
			// 从后往前，找到第一个位于枢轴右边但是小于枢轴的
			while (start < end && pivot <= array[end]) {
				end--;
			}
			// 交换后，枢轴变量下标变为end
			if (start < end) {
				swap(array, start, end);
				start++;
			}
			// 从前往后，找到第一个位于枢轴左边但是大于枢轴的
			while (start < end && pivot >= array[start]) {
				start++;
			}
			// 交换后，枢轴的下标变回start
			if (start < end) {
				swap(array, start, end);
				end--;
			}
		}
		return start;
	}

	/**
	 * 快速排序递归部分
	 *
	 * @param array 待排序数组
	 * @param start 排序范围起始索引
	 * @param end   排序范围终止索引
	 */
	private static void quickSortRecursive(int[] array, int start, int end) {
		int pivotIndex; // 枢轴变量索引
		if (start < end) {
			pivotIndex = partition(array, start, end);
			quickSortRecursive(array, start, pivotIndex - 1); // 先对枢轴左部分递归排序
			quickSortRecursive(array, pivotIndex + 1, end); // 再对枢轴右部分递归排序
		}
	}

	/**
	 * 快速排序
	 *
	 * @param array 待排序数组
	 */
	public static void quickSort(int[] array) {
		quickSortRecursive(array, 0, array.length - 1);
	}

}